/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        123.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/9 15:04
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
//
//设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。
//
//注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
#include "../header.h"

class Solution {
public:
    int maxProfit( vector<int> &prices) {
//        dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1] + prices[i])
//        dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0] - prices[i])
        int dp_i_1_0 = 0, dp_i_2_0 = 0;
        int dp_i_1_1 = INT_MIN, dp_i_2_1 = INT_MIN;
        for (auto price: prices) {
            dp_i_2_1 = max(dp_i_2_1,dp_i_1_0 - price);
            dp_i_2_0 = max(dp_i_2_0,dp_i_2_1 + price);
            dp_i_1_0 = max(dp_i_1_0,dp_i_1_1 + price);
            dp_i_1_1 = max(dp_i_1_1, - price);
        }
        return dp_i_2_0;
    }
};
